package hihocode;

/**
 * Created by shuowu on 2018/1/13.
 */
import java.util.Scanner;

public class KMP{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int testCase = scanner.nextInt();
        scanner.nextLine();
        String pattern = "";
        String string = "";
        for(int i = 1; i <= testCase; i++){
            pattern = scanner.nextLine();
            string = scanner.nextLine();
            System.out.println(kmp(string, pattern));
        }
        scanner.close();
    }

    public static int kmp(String string, String stringPattern){
        if (string == null || stringPattern == null) {
            return stringPattern == string ? 0 : -1;
        }
        char[] chars = string.toCharArray();
        char[] pattern = stringPattern.toCharArray();
        int[] next = new int[pattern.length];
        getNext(pattern, next);
        int k = 0, count = 0;
        for(int i = 0; i < chars.length; i++){
            while(k > 0 && pattern[k] != chars[i]){
                k = next[k - 1];
            }
            if(pattern[k] == chars[i]){
                k++;
            }
            if(k == pattern.length){
                count++;
                k = next[k - 1];
            }
        }
        return count;
    }
    public static void getNext(char[] pattern, int[] next){
        if(pattern == null || pattern.length != next.length){
            return ;
        }
        next[0] = 0;
        int index = 1, k = 0; //k表示匹配串目前的下标
        while(index < pattern.length){
            while(k > 0 && pattern[k] != pattern[index]){
                k = next[k - 1];
            }
            if(pattern[k] == pattern[index]){
                k++;
            }
            next[index] = k;
            index++;
        }
    }
}
